Autonomous vehicles, such as vehicles which do not require a human driver when operating in an autonomous driving mode, may be used to aid in the transport of passengers or items from one location to another. An important component of an autonomous vehicle is the vehicle's map information. This information is critical to allowing the vehicle's computing systems to localize itself and to make appropriate driving decisions for the vehicle. Thus, for vehicles which depend on maps to make driving decisions, it is critical that these maps are kept up to date and accurate. In this regard, changes to the world that make the map out of date or stale, such as when vehicle approaches an entire region of drivable road surface that is not reflected in the map can be extremely concerning. This can occur when a road, lane, driveway, alleyway, etc., is either not included in the original map or is added after the map is built.
Typical approaches for identifying changes to an already mapped road surface, for instance by looking for new or moved lane lines, etc., are simply not capable of detecting new driving surfaces. Other approaches, for instance, such as those that may involve identifying new traffic lights, may not provide sufficient information or context about the surrounding area. This can result in an autonomous vehicle not properly anticipating where another vehicle may come from or where another vehicle may drive into. In turn, these prediction errors can have safety consequences.